The present invention is directed to data processing systems and in particular to error-correction schemes used in such systems.
As the density of data storage has increased in data processing systems, the contents of the storage devices have been subject to more sources of errors. For example, the contents of storage cells in some dynamic memories can be changed even by alpha-particle bombardment. Although the probability that any particular cell will be thus changed within a moderate amount of time is still very small, modern data-processing systems employ arrays of such cells that are so large that the occurrence of data errors is unavoidable.
To deal with such problems, computer designers have resorted to arrangements employing error-correction codes. A typical error-correction code for a multi-bit data word consists of a number of "check bits" that are generated in accordance with a predetermined algorithm. Each possible multi-bit data word is associated with only a single one of the possible sequences of check bits. Therefore, out of all of the possible composite words consisting of the multi-bit data word plus the check bits, only a very small fraction are valid words; if there are N check bits, only one out of every 2.sup.N possible composite words is valid. The error-correction-coding scheme is so arranged that each of the valid composite words is at a large "distance" in a coding-theory sense from every other valid composite word. Error correction, as opposed to detection, can be accomplished for the most-frequent types of errors because the composite word resulting from each of the probable errors is much "closer" to a single valid composite word than it is to any of the other valid composite words. These invalid words are "close" in the sense that they are much more likely to have resulted from errors in that one valid word than they are to have resulted from errors in any other valid word. Consequently, for those invalid words that are "close" to certain valid words, the error-correction circuitry infers that the word should have been the valid word to which the invalid word is closest. Thus, the data-processing system can correct, as well as detect, errors in the data. Of course, some errors are not correctable--in fact, some are not even detectable--but the errors that are most likely to occur can be corrected.
Modern data-processing systems have also been called upon to operate at higher speeds. Unfortunately, the requirement for error correction is not entirely consistent with that for speed. The correction algorithms that use error-correction codes to correct erroneous data can be quite time-consuming. Although use of the correction algorithms is necessary when a data error occurs, correction hardware, in the form, for example, of gates in the path from the system memory to the system processor, typically adds delays even in the absence of errors. Furthermore, an error-correction code must be calculated whenever a data word is stored in the system memory, and the required calculation time can delay retrieval of the associated data word.
It is accordingly an object of the present invention to provide error correction in a system that does not require the presence of the error-correction gates in the signal path from the memory to the instruction-execution portion of the system. It is another object of the present invention to reduce the delay caused by the error-correction process.
It is an object of another aspect of the invention to afford the benefits of an error-correction-coding scheme while eliminating the possible delay required by error-correction-code generation.